package leetcode.code0934;

import java.util.LinkedList;
import java.util.Queue;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	int m, n;
	Queue<int[]> q;
	int[][] grid;
	int[] direction = new int[] { 0, -1, 0, 1, -1, 0, 1, 0 };
	int flag;

	public int shortestBridge(int[][] grid) {
		this.m = grid.length;
		this.n = grid[0].length;
		this.q = new LinkedList<>();
		this.grid = grid;
		this.flag = 2;
		A: for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (grid[i][j] == 1) {
					this.mark(i, j);
					break A;
				}
			}
		}
		int ans = 0;
		B: while (!q.isEmpty()) {
			int size = q.size();
			while (size > 0) {
				int[] cur = q.poll();
				for (int k = 0; k < 8; k += 2) {
					if (this.bridge(cur[0] + direction[k], cur[1] + direction[k + 1])) {
						break B;
					}
				}
				size--;
			}
			ans += 1;
		}
		return ans;
	}

	private boolean bridge(int i, int j) {
		if (i >= 0 && i < m && j >= 0 & j < n) {
			if (this.grid[i][j] == 1) {
				return true;
			} else if (this.grid[i][j] == 0) {
				this.grid[i][j] = this.flag;
				q.add(new int[] { i, j });
			}
		}
		return false;
	}

	private void mark(int i, int j) {
		if (i >= 0 && i < m && j >= 0 & j < n) {
			if (this.grid[i][j] == 1) {
				this.grid[i][j] = this.flag;
				q.add(new int[] { i, j });
				for (int k = 0; k < 8; k += 2) {
					this.mark(i + direction[k], j + direction[k + 1]);
				}
			}
		}
	}

	@Override
	public void debug1() {
		HelpDebug.compare(1, this.shortestBridge(HelpDebug.str2array1("[[0,1],[1,0]]")));

	}

	@Override
	public void debug2() {
		HelpDebug.compare(2, this.shortestBridge(HelpDebug.str2array1("[[0,1,0],[0,0,0],[0,0,1]]")));

	}

	@Override
	public void debug3() {
		HelpDebug.compare(1, this
				.shortestBridge(HelpDebug.str2array1("[[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]")));

	}

	@Override
	public void debug4() {
		HelpDebug.compare(1, this.shortestBridge(HelpDebug.str2array1("[[0,1],[1,0]]")));

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug3();
		so.debug1();
		so.debug2();
		so.debug4();

	}

}
